package com.origin.niuke.binarySearch;

/**
 * 长度最小的连续子数组
 * 给定一个数组 nums 和一个正整数 target , 找出满足和大于等于 target 的长度最短的连续子数组并返回其长度，如果不存在这种子数组则返回 0。
 * 输入：[1,2,4,4,1,1,1],9
 * 返回值：3
 * 算法：二分 + 前缀和、双指针
 *
 * @author yezh
 * @date 2023/2/15 21:14
 */
public class NC202 {

    public static void main(String[] args) {
        // [0, 1] prefix[2] - prefix[0]
        // [1, 2] prefix[3] - prefix[1]
        System.out.println(new NC202().minSubarray_point(new int[]{1, 2, 4, 4, 1, 1, 1}, 9));
    }

    public int minSubarray(int[] nums, int target) {
        // write code here
        int n = nums.length, ans = Integer.MAX_VALUE;
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + nums[i - 1];
        // [i, j] 的总和 = prefix[j + 1] - prefix[i]
        // prefix[j + 1] - prefix[i] >= target ==> prefix[j + 1] >= target + prefix[i]
        for (int i = 0; i < n; i++) {
            int end = binarySearch(prefix, i + 1, n, target + prefix[i]);
            if (end < 0 || end >= n + 1) continue;
            ans = Math.min(ans, end - i);
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    int binarySearch(int[] nums, int l, int r, int target) {
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (target > nums[mid]) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    public int minSubarray_point(int[] nums, int target) {
        int ans = Integer.MAX_VALUE;
        for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum > target) {
                ans = Math.min(ans, r - l + 1);
                sum -= nums[l++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

}
